Cryptosystems are becoming increasingly important especially as data communication becomes ubiquitous. No longer limited to military applications, cryptosystems are being used commercially for such applications as privacy systems, authentication, and digital signatures. Privacy systems prevent the extraction of information transmitted through or stored in a medium by unauthorized parties. Identification is used, for example, in cellular phone communications to prevent fraudulent access to a customer account. And, digital signature systems are used to verify the authenticity of a message.
One of the most significant contributions to the field of cryptography was made by Diffie-Hellman (DH) with the concept of public key cryptographic systems. The core realization was the fact that practically secure systems can be built that require no secure transfer of any secret key. Previously, it was thought that a secure cryptosystem relied on the prior agreement between the sending and receiving parties concerning the key used to encrypt the data. If the secrecy of this key was ever prejudiced, the secrecy of the cryptosystem was also at risk.
The critical innovation of Diffie-Hellman was the concept of the one-way function. Such a function is defined as a function f such that for every x in the domain of f, f(x) is easy to compute; but for virtually all y in the range of f, it is computationally infeasible to find an x such that y=f(x). Also discovered was the concept of the trapdoor one-way function. These functions are defined as a family of invertible functions f.sub.z, indexed by z, such that, given z, it is easy to find algorithms E.sub.z and D.sub.z that easily compute f.sub.z (x) and f.sub.z.sup.-1 (y) for all x and y in the domain and range, respectively, of f.sub.z. It is computationally infeasible to compute f.sub.z.sup.-1 (y) even assuming E.sub.z is known, if z is not known.
RSA is considered to be the first usable public key cryptosystem. This particular cryptosystem is based on the difficulty of factoring very large numbers, and today, it is still the most widely used public-key cryptosystem in the world. Since then, in the field of computational number theory, major work has been done towards efficient integer factorization. As a consequence, new types of public-key algorithms have arisen. The most important competitors to RSA are schemes based on the Discrete Logarithm (DL) problem. Originally, the DL problem was considered in the multiplicative group of a finite field, especially a prime field or a field of characteristic 2, since these fields seemed most appropriate for implementations. Then in 1985, a variant of the DL problem was proposed based on the group of points of an elliptic curve (EC) over a finite field.
A main feature that makes elliptic curves attractive is the relatively short operand length. Cryptosystems that explore the DL problem over elliptic curves can be built with an operand length of 140-200 bits as compared to RSA and systems based on the DL in finite fields, both of which require operands of 512-1024 bits. Other advantages are the large numbers of curves that are available to provide the groups and the absence of sub-exponential time algorithms (such as the index calculus method) to attack EC cryptosystems. The latter property provides a very good long-term security against current attacks. In addition, IEEE and other standard bodies such as ANSI and ISO are in the process of standardizing EC cryptosystems.